/***************************************************************
* M3D_SPL.CPP
*
* Splines support
***************************************************************/
#include <m3d/m3d_stdafx.h>
#include <string.h>
#include <ap_comm.h>
#include <m3d.h>
#include <fileio.h>

namespace {

struct CHUNK_SCALE {
   float       base, range;
};

#define CHUNK_MAX_PACKED_TRACKS    4

typedef DWORD CHUNK_INFO;

const DWORD CHI_IS_BYTES_OFS        = 0;
const DWORD CHI_IS_BYTES_MASK       = ((1 << CHUNK_MAX_PACKED_TRACKS) - 1) << CHI_IS_BYTES_OFS;

const DWORD CHI_IS_CONST_OFS        = CHUNK_MAX_PACKED_TRACKS;
const DWORD CHI_IS_CONST_MASK       = ((1 << CHUNK_MAX_PACKED_TRACKS) - 1) << CHI_IS_CONST_OFS;

const DWORD CHI_OFS_OFS             = CHI_IS_CONST_OFS + CHUNK_MAX_PACKED_TRACKS;
const DWORD CHI_OFS_MASK            = (DWORD)-1 - CHI_IS_BYTES_MASK - CHI_IS_CONST_MASK;

#define CHI_GET_IS_BYTES(a)         (((a) & CHI_IS_BYTES_MASK) >> CHI_IS_BYTES_OFS)
#define CHI_GET_IS_CONST(a)         (((a) & CHI_IS_CONST_MASK) >> CHI_IS_CONST_OFS)
#define CHI_GET_OFS(a)              (((a) & CHI_OFS_MASK) >> CHI_OFS_OFS)

#define CHI_IS_BYTES(a, t)          ((a) & (1 << (CHI_IS_BYTES_OFS + t)))
#define CHI_IS_CONST(a, t)          ((a) & (1 << (CHI_IS_CONST_OFS + t)))

#define CHI_SET_IS_BYTES(a,v)       (a) = ((a) & ((DWORD)-1 - CHI_IS_BYTES_MASK)) + (((v) << CHI_IS_BYTES_OFS) & CHI_IS_BYTES_MASK)
#define CHI_SET_IS_CONST(a,v)       (a) = ((a) & ((DWORD)-1 - CHI_IS_CONST_MASK)) + (((v) << CHI_IS_CONST_OFS) & CHI_IS_CONST_MASK)
#define CHI_SET_OFS(a,v)            (a) = ((a) & ((DWORD)-1 - CHI_OFS_MASK)) + (((v)  << CHI_OFS_OFS) & CHI_OFS_MASK)

struct CHUNK_SPLINE {
   WORD        constMask;
   BYTE        chunkKeys;
   BYTE        __unsued;
};

enum {
   // NEVER REMOVE OR INSERT ANY CHUNK IDS, JUST ADD NEW ONES AT THE END
   CNK_SPL_TYPE = FIO_CNK_USER,
   CNK_SPL_STATE,
   CNK_SPL_VALUE_DIM,
   CNK_SPL_DATA_DIM,
   CNK_SPL_NKP,
   CNK_SPL_DATASIZE,
   CNK_SPL_DATA
};

} // namespace 

struct CHUNK_WRITE_BUF {
   BYTE        *pData;
   int         dataAllocated;
   int         dataSize;

   CHUNK_WRITE_BUF   (void) : pData(0), dataAllocated(0), dataSize(0) {}
   ~CHUNK_WRITE_BUF  (void) { free(pData); }
   
   template <class T>
   T*          At          (int ofs)            { return (T*)(pData + ofs); }

   void        Clear       (void)               { dataSize = 0; }
   void        StoreBytes  (void *v, int n)     { int o = Reserve(n); memcpy(pData + o, v, n); }
   void        StoreByte   (BYTE v)             { StoreBytes(&v, sizeof(BYTE)); }
   void        StoreWord   (WORD v)             { StoreBytes(&v, sizeof(WORD)); }
   void        StoreDword  (DWORD v)            { StoreBytes(&v, sizeof(DWORD)); }
   void        StoreFloat  (float v)            { StoreBytes(&v, sizeof(float)); }
   int         Reserve     (int n)
   {
      if (dataSize + n > dataAllocated) {
         dataAllocated  = max(dataSize + n, dataAllocated * 2);
         pData          = (BYTE*)realloc(pData, dataAllocated);
      }
      dataSize += n;
      return dataSize - n;
   }
};

struct CHUNK_READ_BUF {
   BYTE        *ptr;

   BYTE        ReadByte    (void)               { BYTE  v = *ptr; ptr += sizeof(BYTE); return v; }
   WORD        ReadWord    (void)               { WORD  v = *(WORD*)ptr; ptr += sizeof(WORD); return v; }
   //DWORD       ReadDword   (void)               { DWORD v = *(DWORD*)ptr; ptr += sizeof(DWORD); return v; }
   //float       ReadFloat   (void)               { float v = *(float*)ptr; ptr += sizeof(float); return v; }
   void        Skip        (int n)              { ptr += n; }
};

/***************************************************************
 * m3dSPL_OPTIMIZE::m3dSPL_OPTIMIZE ()
 *
 **************************************************************/
m3dSPL_OPTIMIZE::m3dSPL_OPTIMIZE( int _state, float _maxErrorConst, float _maxErrorPack, float _maxHalfRateError)
{
   state             = _state;
   maxErrorPack      = _maxErrorPack;
   maxErrorConst     = _maxErrorConst;
   maxHalfRateError  = _maxHalfRateError;
   minChunk          = 4;
   maxChunk          = 64;
   return;
}

/***************************************************************
 * m3dSPL_INFO::m3dSPL_INFO ()
 *
 **************************************************************/
m3dSPL_INFO::m3dSPL_INFO(void)
{
   memUsed           = 0;
   numChunks         = 0;
   numChunksWoDim    = 0;
   minChunkSize      = 0x7FFFFFF;
   maxChunkSize      = 0;
   sumChunkSize      = 0;
   numConstTracks    = 0;
   numConstChunks    = 0;
   numByteChunks     = 0;
   numWordChunks     = 0;
   numMergedChunks   = 0;
   return;
}

/***************************************************************
 * m3dSPL_INFO::operator +=()
 *
 **************************************************************/
m3dSPL_INFO& m3dSPL_INFO::operator +=(const m3dSPL_INFO &i)
{
   memUsed           += i.memUsed;
   numChunks         += i.numChunks;
   numChunksWoDim    += i.numChunksWoDim;
   minChunkSize      = min(minChunkSize, i.minChunkSize);
   maxChunkSize      = max(maxChunkSize, i.maxChunkSize);
   sumChunkSize      += i.sumChunkSize;
   numConstTracks    += i.numConstTracks;
   numConstChunks    += i.numConstChunks;
   numByteChunks     += i.numByteChunks;
   numWordChunks     += i.numWordChunks;
   numMergedChunks   += i.numMergedChunks;
   return *this;
}

m3dSPL_INFO    sumSplInfo;

//
// class m3dSPL
//
/***************************************************************
 * m3dSPL::Make ()
 *
 **************************************************************/
m3dSPL* m3dSPL::Make(int type, int nKp)
{
   m3dSPL   *pSpl = NULL;

   switch (type) {
      case M3D_SPL_LINEAR1D:
         pSpl = apNEW m3dSPL_LINEAR1D();
         break;
      case M3D_SPL_LINEAR2D:
         pSpl = apNEW m3dSPL_LINEAR2D();
         break;
      case M3D_SPL_LINEAR3D:
         pSpl = apNEW m3dSPL_LINEAR3D();
         break;
      case M3D_SPL_HERMIT:
         pSpl = apNEW m3dSPL_HERMIT();
         break;
      case M3D_SPL_BEZIER2D:  
         pSpl = apNEW m3dSPL_BEZIER2D();
         break;
      case M3D_SPL_BEZIER3D:  
         pSpl = apNEW m3dSPL_BEZIER3D();
         break;
      case M3D_SPL_LAGRANGE:
         pSpl = apNEW m3dSPL_LAGRANGE();
         break;
      case M3D_SPL_QUAT:
         pSpl = apNEW m3dSPL_QUAT();
         break;
      case M3D_SPL_COLOR:
         pSpl = apNEW m3dSPL_COLOR();
         break;
      default:
         ASSERT(FALSE);
   }

   pSpl->AllocSpline(nKp);
   
   return pSpl;
}

/***************************************************************
* m3dSPL::m3dSPL()
*
***************************************************************/
m3dSPL::m3dSPL(int type, int kpSize, int valSize)
{
   ASSERT(kpSize > sizeof(float) && (kpSize & 3) == 0);
   ASSERT(valSize <= kpSize && (valSize & 3) == 0);
   
   this->type     = type;
   this->dataDim  = kpSize / sizeof(float) - 1;    // -arg
   this->valDim   = valSize / sizeof(float);

   nKp      = 0;
   dataSize = 0;
   pData    = NULL;

   return;
}

/*************************************************************
'* m3dSPL::m3dSPL()
'* 
'*************************************************************/
m3dSPL::m3dSPL(const m3dSPL &from)
   : state   (from.state)
   , type    (from.type)
   , valDim  (from.valDim)
   , dataDim (from.dataDim)
   , nKp     (from.nKp)
   , dataSize(from.dataSize)
   , pData   (NULL)
{ 
   // alloc memory for data if needed
   if (dataSize > 0) {
      pData = (BYTE*)realloc(pData, dataSize);
      memcpy(pData, from.pData, from.dataSize);
   }
}


/***************************************************************
* m3dSPL::~m3dSPL ()
*
***************************************************************/
m3dSPL::~m3dSPL (void)
{
   free(pData);
   return;
}

/***************************************************************
* m3dSPL::GetRaw ()
*
***************************************************************/
const m3dSPL_KP&  m3dSPL::GetRaw (int i) const 
{
   ASSERT(!state.Is(M3D_SPL_ST_CHUNKED | M3D_SPL_RAW_ST_NO_ARG));
   STRONG_ASSERT(i >= 0 && i < nKp);
   return *(m3dSPL_KP*)(pData + i * GetRawKpSize());
}

/***************************************************************
* m3dSPL::GetRaw ()
*
***************************************************************/
m3dSPL_KP& m3dSPL::GetRaw (int i) 
{
   ASSERT(!state.Is(M3D_SPL_ST_CHUNKED | M3D_SPL_RAW_ST_NO_ARG));
   STRONG_ASSERT(i >= 0 && i < nKp);
   return *(m3dSPL_KP*)(pData + i * GetRawKpSize());
}

/***************************************************************
* m3dSPL::GetRawDataPtr ()
*
***************************************************************/
float* m3dSPL::GetRawDataPtr (int i) 
{
   ASSERT(!state.Is(M3D_SPL_ST_CHUNKED));
   STRONG_ASSERT(i >= 0 && i < nKp);
   return (float*)(pData + i * GetRawKpSize() + (state.Is(M3D_SPL_RAW_ST_NO_ARG) ? 0 : sizeof(float)));
}

/***************************************************************
* m3dSPL::GetRawDataPtr ()
*
***************************************************************/
const float* m3dSPL::GetRawDataPtr (int i) const 
{
   ASSERT(!state.Is(M3D_SPL_ST_CHUNKED));
   STRONG_ASSERT(i >= 0 && i < nKp);
   return (float*)(pData + i * GetRawKpSize() + (state.Is(M3D_SPL_RAW_ST_NO_ARG) ? 0 : sizeof(float)));
}

/***************************************************************
* m3dSPL::AllocSpline()
*
***************************************************************/
void m3dSPL::AllocSpline(int _nKp)
{
   state.Fill(0);
   nKp = _nKp;
   
   //BYTE *o = pData;
   dataSize = nKp * GetRawKpSize();
   pData = (BYTE*)realloc(pData, dataSize);
   
   return;
}

/***************************************************************
* m3dSPL::AllocSplineZeroMem()
*
***************************************************************/
void m3dSPL::AllocSplineZeroMem(int _nKp)
{
   int prevSize = nKp*GetRawKpSize();

   state.Fill(0);
   nKp = _nKp;

   //BYTE *o = pData;
   dataSize = nKp * GetRawKpSize();
   pData = (BYTE*)realloc(pData, dataSize);

   if (pData && prevSize < dataSize) {
      memset(pData + prevSize, 0, dataSize - prevSize);
   }

   return;
}

/***************************************************************
* m3dSPL::RemoveKp()
*
***************************************************************/
void m3dSPL::RemoveKp(int kpNmb, int nRemove)
{
   if (nRemove == 0 || nKp <= 1) {
      return;
   }

   if (state.Is(M3D_SPL_ST_CHUNKED)) { // remove from optimized splines not supported
      ASSERT(0);
      return;
   }

   ASSERT(kpNmb >=0 && kpNmb + nRemove <= nKp);

   int dstOfs = kpNmb                     * GetRawKpSize();
   int srcOfs = (kpNmb + nRemove)         * GetRawKpSize();
   int size   = (nKp - (kpNmb + nRemove)) * GetRawKpSize();

   memcpy(pData + dstOfs, pData + srcOfs, size);

   dataSize -= nRemove * GetRawKpSize();
   pData = (BYTE*)realloc(pData, dataSize);
   nKp -= nRemove;

   return;
}

/***************************************************************
* m3dSPL::AddKp()
*
***************************************************************/
void m3dSPL::AddKp (int numKp)
{
   if (numKp <= 0) {
      return;
   }

   if (state.Is(M3D_SPL_ST_CHUNKED)) { // insert to optimized splines not supported
      ASSERT(0);
      return;
   }

   dataSize += numKp * GetRawKpSize();
   pData = (BYTE*)realloc(pData, dataSize);

   nKp += numKp;

   return;
}

/***************************************************************
* m3dSPL::RemoveKp()
*
***************************************************************/
void m3dSPL::InsertKp(int kpNmb, int nInsert)
{
   if (nInsert == 0) {
      return;
   }

   if (state.Is(M3D_SPL_ST_CHUNKED)) { // insert to optimized splines not supported
      ASSERT(0);
      return;
   }

   ASSERT(kpNmb >=0 && kpNmb <= nKp);

   int dstOfs = (kpNmb + nInsert)      * GetRawKpSize();
   int srcOfs = kpNmb                  * GetRawKpSize();
   int size   = (nKp - kpNmb)          * GetRawKpSize();

   dataSize += nInsert * GetRawKpSize();
   pData = (BYTE*)realloc(pData, dataSize);

   if (size > 0) {
      memmove(pData + dstOfs, pData + srcOfs, size);
   }

   nKp += nInsert;

   return;
}

/***************************************************************
* m3dSPL::GetKpArg()
*
***************************************************************/
float m3dSPL::GetKpArg(int kpNmb) const
{
   if (IsIntArg()) {
      if (state.Is(M3D_SPL_ST_HALFRATE)) {
         return (float)(kpNmb * 2);
      } else {
         return (float)kpNmb;
      }
   }
   return GetRaw(kpNmb).arg;
}

/***************************************************************
* m3dSPL::GetKpValue()
*
***************************************************************/
void m3dSPL::GetKpValue(int kpNmb, void *pValue) const
{
   if (state.Is(M3D_SPL_ST_CHUNKED)) {
      if (dataDim == valDim) {
         GetKpDataChunk(kpNmb, (float*)pValue);
      } else {
         float tmp[M3D_SPL_MAX_KP_DIM];
         GetKpDataChunk(kpNmb, tmp);
         memcpy(pValue, tmp, valDim * sizeof(float));
      }
   } else {
      const BYTE *p = pData + kpNmb * GetRawKpSize();
      if (!IsIntArg()) {
         p += sizeof(float);
      }
      memcpy(pValue, p, valDim * sizeof(float));
   }

   return;
}

/***************************************************************
* m3dSPL::GetKpData()
*
***************************************************************/
void m3dSPL::GetKpData(int kpNmb, void *pValue) const
{
   if (state.Is(M3D_SPL_ST_CHUNKED)) {
      GetKpDataChunk(kpNmb, (float*)pValue);
   } else {
      const BYTE *p = pData + kpNmb * GetRawKpSize();
      if (!IsIntArg()) {
         p += sizeof(float);
      }
      memcpy(pValue, p, dataDim * sizeof(float));
   }
   return;
}

/***************************************************************
* m3dSPL::GetKp()
*
***************************************************************/
void m3dSPL::GetKp(int kpNmb, m3dSPL_KP *pValue) const
{
   pValue->arg = GetKpArg(kpNmb);
   
   if (state.Is(M3D_SPL_ST_CHUNKED)) {
      GetKpDataChunk(kpNmb, &pValue->arg + 1);
   } else {
      const BYTE *p = pData + kpNmb * GetRawKpSize();
      if (!IsIntArg()) {
         p += sizeof(float);
      }
      memcpy(&pValue->arg + 1, p, dataDim * sizeof(float));
   }
   return;
}

/***************************************************************
* m3dSPL::SetKpArg()
*
***************************************************************/
void m3dSPL::SetKpArg(int kpNmb, float arg)
{
   if (IsIntArg()) {
      ASSERT(0);
      return;
   }

   GetRaw(kpNmb).arg = arg;

   return;
}

/***************************************************************
* m3dSPL::SetKpValue()
*
***************************************************************/
void m3dSPL::SetKpValue(int kpNmb, const void *pValue)
{
   if (state.Is(M3D_SPL_ST_CHUNKED)) {
      ASSERT(0);
      return;
   }

   BYTE *p = pData + kpNmb * GetRawKpSize();
   if (!IsIntArg()) {
      p += sizeof(float);
   }
   memcpy(p, pValue, valDim * sizeof(float));

   return;
}

/***************************************************************
* m3dSPL::SetKpData()
*
***************************************************************/
void m3dSPL::SetKpData(int kpNmb, const void *pValue)
{
   if (state.Is(M3D_SPL_ST_CHUNKED)) {
      ASSERT(0);
      return;
   }
   
   BYTE *p = pData + kpNmb * GetRawKpSize();
   if (!IsIntArg()) {
      p += sizeof(float);
   }
   memcpy(p, pValue, dataDim * sizeof(float));
   
   return;
}

/***************************************************************
* m3dSPL::SetKp()
*
***************************************************************/
void m3dSPL::SetKp(int kpNmb, const m3dSPL_KP *pValue)
{
   if (state.Is(M3D_SPL_ST_CHUNKED)) {
      ASSERT(0);
      return;
   }

   SetKpArg(kpNmb, pValue->arg);
   SetKpData(kpNmb, &pValue->arg + 1);

   return;
}


/***************************************************************
 * m3dSPL::FindSeg ()
 *    Find spline segment using binary search
 **************************************************************/
int m3dSPL::FindSeg (float arg) const
{
   if (nKp <= 1) {
      return FIND_SEG_LEFT;
   }
   
   if (IsIntArg()) {
      if (state.Is(M3D_SPL_ST_HALFRATE)) {
         arg *= 0.5f;
      }
      
      if (arg < M3D_EPSILON) {
         return FIND_SEG_LEFT;
      }
      if (arg > nKp - 1.f - M3D_EPSILON) {
         return FIND_SEG_RIGHT;
      }

      int argInt = min(nKp-2, m3dIntFloor(arg));
      ASSERT(argInt == (int)(arg) || m3dIsEqual((float)arg - 1.f, (float)(nKp - 2)));
      
      return argInt;
   }


   if (arg <= GetKpArg(0)) {
      return FIND_SEG_LEFT;
   }
   if (arg >= GetKpArg(nKp - 1)) {
      return FIND_SEG_RIGHT;
   }

   int firstInd = 0;
   int lastInd  = nKp - 1;
   while (lastInd - firstInd > 1) {
      int   ind    = (firstInd + lastInd) / 2;
      float curArg = GetKpArg(ind);
      if (arg < curArg) {
         lastInd  = ind;
      } else {
         firstInd = ind;
      } 
   }
  
   return firstInd;
}

/***************************************************************
 * m3dSPL::FindSeg ()
 *    Find spline segment using binary search, 
 *    return true if interpolation required
 **************************************************************/
BOOL m3dSPL::FindSeg (float arg, m3dSPL_KP *pKp1, m3dSPL_KP *pKp2) const
{
   int segNmb;

   segNmb = FindSeg(arg);

	if (segNmb == FIND_SEG_LEFT) {
      GetKp(0, pKp1);
      return FALSE;
   }
	if (segNmb == FIND_SEG_RIGHT) {
      GetKp(nKp - 1, pKp1);
      return FALSE;
   }
   
   GetKp(segNmb,   pKp1);
   GetKp(segNmb+1, pKp2);
   
   return TRUE;
}

/***************************************************************
* m3dSPL::GetMinMaxValue ()
*
***************************************************************/
void m3dSPL::GetMinMaxValue(float start, float end, float step, void *minValue, void *maxValue)
{
   int    i, j, nSamples;
   float  arg;
   float  value[M3D_SPL_MAX_KP_DIM];
   
   for (i = 0; i < valDim; i ++) {
      ((float*)minValue)[i] =  M3D_INFINITY;
      ((float*)maxValue)[i] = -M3D_INFINITY;
   }
   nSamples = min(nKp, m3dIntCeil((end - start) / step) + 1);
   
   for (i = 0; i < nSamples; i ++) {
      arg = start + i * step;

      GetValue(arg, (void*)value);
      
      for (j = 0; j < valDim; j ++) {
         ((float*)minValue)[j] = min(((float*)minValue)[j], value[j]);
         ((float*)maxValue)[j] = max(((float*)maxValue)[j], value[j]);
      }
   }
   return;
}

/***************************************************************
* m3dSPL::GetMinMaxValue ()
*
***************************************************************/
void m3dSPL::GetKpDataBaseRange(int startKp, int numKp, float *ofs, float *range, float *maxHalfError) const
{
   ASSERT(numKp > 0);
   
   for (int t = 0; t < dataDim; t++) {
      ofs[t] = M3D_INFINITY;
      range[t] = -M3D_INFINITY;
   }
   
   if (maxHalfError) {
      *maxHalfError = 0.0f;
   }
   
   for (int k = startKp; k < startKp + numKp; k++) {
      float val[M3D_SPL_MAX_KP_DIM];
      GetKpData(k, val);
      
      for (int t = 0; t < dataDim; t++) {
         ofs[t] = min(ofs[t], val[t]);
         range[t] = max(range[t], val[t]);
      }

      if (maxHalfError && ((k - startKp) & 1) && k != startKp + numKp - 1) {
         float prev[M3D_SPL_MAX_KP_DIM];
         float next[M3D_SPL_MAX_KP_DIM];
         GetKpData(k - 1, prev);
         GetKpData(k + 1, next);
         for (int t = 0; t < dataDim; t++) {
            float err = m3dFAbs(val[t] - (prev[t] + next[t]) * 0.5f);
            *maxHalfError = max(*maxHalfError, err);
         }
      }
   }

   for (int t = 0; t < dataDim; t++) {
      range[t] -= ofs[t];
   }

   return;
}

/***************************************************************
* m3dSPL::Duplicate()
*
***************************************************************/
m3dSPL* m3dSPL::Duplicate(void) const
{
   m3dSPL *pSpl = m3dSPL::Make(type);
   if (!pSpl) {
      return NULL;
   }
   
   *pSpl = *this;
   return pSpl;
}

/***************************************************************
* m3dSPL::Swap()
*
***************************************************************/
void m3dSPL::Swap(m3dSPL *spl)
{
   BYTE *myData      = pData;
   int  myDataSize   = dataSize;
   BYTE *otherData   = spl->pData;
   int  otherDataSize= spl->dataSize;
   
   pData = spl->pData = NULL;
   dataSize = spl->dataSize = 0;

   m3dSPL_LINEAR1D t = *(m3dSPL_LINEAR1D*)spl;
   *spl = *this;
   *this = t;

   pData = otherData;
   dataSize = otherDataSize;

   spl->pData = myData;
   spl->dataSize = myDataSize;
   
   return;
}

/*************************************************************
'* m3dSPL::operator=()
'* 
'*************************************************************/
m3dSPL& m3dSPL::operator=(const m3dSPL &from)
{
   STRONG_ASSERT(type     == from.type   );
          ASSERT(valDim   == from.valDim );
          ASSERT(dataDim  == from.dataDim);

   state    = from.state;
   nKp      = from.nKp;

   if ((dataSize != 0) || (from.dataSize != 0)) {
      pData = (BYTE*)realloc(pData, from.dataSize);
      memcpy(pData, from.pData, from.dataSize);
   } else {
      pData = NULL;
   }

   dataSize = from.dataSize;

   return *this;
}

/***************************************************************
* m3dSPL::CheckForIntArg()
*
***************************************************************/
BOOL m3dSPL::CheckForIntArg(void)
{
   if (IsIntArg()) {
      return TRUE;
   }

   for (int k = 0; k < nKp; k++) {
      if (!m3dIsEqual((float)k * (state.Is(M3D_SPL_ST_HALFRATE) ? 2.0f : 1.0f), GetKpArg(k))) {
         return FALSE;
      }
   }

   return TRUE;
}

/***************************************************************
* m3dSPL::Sample()
*
***************************************************************/
m3dSPL* m3dSPL::Sample(float start, float end, float step) const
{
   m3dSPL *pSpl = m3dSPL::Make(type);
   if (!pSpl) {
      return NULL;
   }

   pSpl->AllocSpline(m3dIntCeil((end - start) / step) + 1);

   for (int i = 0; i < pSpl->NKp(); i++) {
      float value[M3D_SPL_MAX_KP_DIM];
      float arg = start + i * step;

      GetValue(arg, value);
      pSpl->SetKpArg(i, arg);
      pSpl->SetKpValue(i, value);
   }

   return pSpl;
}

__INLINE int _numBits(int a)
{
   int n = 0;
   while (a) {
      if (a & 1) {
         n++;
      }
      a >>= 1;
   }
   return n;
}


/***************************************************************
* m3dSPL::_reoderFloat()
*
***************************************************************/
__INLINE void _reoderDword(DWORD &f)
{
   BYTE *a = (BYTE*)&f;
   BYTE t;
   t = a[0]; a[0] = a[3]; a[3] = t;
   t = a[1]; a[1] = a[2]; a[2] = t;
   return;
}

/***************************************************************
* m3dSPL::_reoderFloat()
*
***************************************************************/
__INLINE void _reoderFloat(float &f)
{
   _reoderDword(*(DWORD*)&f);
   return;
}

/***************************************************************
* m3dSPL::_reoderWord()
*
***************************************************************/
__INLINE void _reoderWord(WORD &f)
{
   BYTE *a = (BYTE*)&f;
   BYTE t;
   t = a[0]; a[0] = a[1]; a[1] = t;
   return;
}


/***************************************************************
* m3dSPL::ByteReorder()
*
***************************************************************/
void m3dSPL::ByteReorder(void)
{
   if (!state.Is(M3D_SPL_ST_CHUNKED)) {
      ASSERT(dataSize % sizeof(float) == 0);
      float *f = (float*)pData;
      for (int i = 0; i < dataSize / sizeof(float); i ++) {
         _reoderFloat(f[i]);
      }
      return;
   }

   CHUNK_SPLINE   *pSpline       = (CHUNK_SPLINE*)pData;
   CHUNK_SCALE    *splTm         = (CHUNK_SCALE*)(pData + sizeof(CHUNK_SPLINE));
   CHUNK_INFO     *chunkTbl      = (CHUNK_INFO*)((BYTE*)splTm + dataDim * sizeof(CHUNK_SCALE));

#ifdef _AP_BIG_ENDIAN
   _reoderWord(pSpline->constMask);
#endif

   for (int t = 0; t < dataDim; t++) {
      _reoderFloat(splTm[t].base);
      _reoderFloat(splTm[t].range);
   }

   int numChunks        = ((nKp + pSpline->chunkKeys - 1) / pSpline->chunkKeys);

   BYTE *lastData = NULL;
   
   for (int c = 0; c < numChunks; c++) {
      CHUNK_INFO &cnk = chunkTbl[c];

#ifdef _AP_BIG_ENDIAN
      _reoderDword(*(DWORD*)&cnk);
#endif      

      // get ptr to chunk
      BYTE *data           = pData + CHI_GET_OFS(cnk);

      if (data <= lastData) {
#ifndef _AP_BIG_ENDIAN
         _reoderDword(*(DWORD*)&cnk);
#endif
         continue; // this chunk already reordered
      }
      lastData = data;

      DWORD constMask      = pSpline->constMask;
      DWORD cnkBytes       = CHI_GET_IS_BYTES(cnk);
      DWORD cnkConst       = CHI_GET_IS_CONST(cnk);

      // convert chunk header (0 for spline-const track, 1 word for chunk-const track, 2 words for other)
      for (int t = 0; t < dataDim; t++) {
         if (constMask & (1<<t)) {
            continue;
         }
         // chunk base
         _reoderWord(*(WORD*)data);
         data += sizeof(WORD);

         if ((cnkConst & (1<<t)) == 0) {
            // chunk scale
            _reoderWord(*(WORD*)data);
            data += sizeof(WORD);
         }
      }

      // reorder chunk keypoints data
      constMask |= cnkConst;

      int numKey = min<int>(pSpline->chunkKeys, nKp - c * pSpline->chunkKeys);
      for (int k = 0; k < numKey; k++) {
         for (int t = 0; t < dataDim; t++) {
            if (constMask & (1<<t)) {
               ;
            } else if (cnkBytes & (1<<t)) {
               data += sizeof(BYTE);
            } else {
               _reoderWord(*(WORD*)data);
               data += sizeof(WORD);
            }
         }
      }

#ifndef _AP_BIG_ENDIAN
      _reoderDword(*(DWORD*)&cnk);
#endif

      ASSERT(data <= pData + dataSize);
   }

#ifndef _AP_BIG_ENDIAN
   _reoderWord(pSpline->constMask);
#endif

   return;
}

/***************************************************************
* m3dSPL::GetInfo()
*
***************************************************************/
void m3dSPL::GetInfo(m3dSPL_INFO &info) const
{
   info = m3dSPL_INFO();
   info.memUsed = dataSize;

   if (state.Is(M3D_SPL_ST_CHUNKED)) {
      CHUNK_SPLINE   *pSpline       = (CHUNK_SPLINE*)pData;
      CHUNK_SCALE    *splTm         = (CHUNK_SCALE*)(pData + sizeof(CHUNK_SPLINE));
      CHUNK_INFO     *chunkTbl      = (CHUNK_INFO*)((BYTE*)splTm + dataDim * sizeof(CHUNK_SCALE));

      int numChunks        = ((nKp + pSpline->chunkKeys - 1) / pSpline->chunkKeys);
      info.numChunksWoDim  = numChunks;
      info.numConstTracks  = _numBits(pSpline->constMask);

      info.minChunkSize    = pSpline->chunkKeys;
      info.maxChunkSize    = pSpline->chunkKeys;
      //int chunkInBlock     = dataDim - info.numConstChunks;

      int prevChunkOfs = -1;
      
      for (int c = 0; c < numChunks; c++) {
         CHUNK_INFO &cnk = chunkTbl[c];
         
         for (int t = 0; t < dataDim; t++) {
            if (pSpline->constMask & (1<<t)) {
               continue;
            }
            
            info.numChunks++;
            if (CHI_IS_CONST(cnk, t)) {
               info.numConstChunks++;
            } else if (CHI_IS_BYTES(cnk, t)) {
               info.numByteChunks++;
            } else {
               info.numWordChunks++;
            }
         }

         if (CHI_GET_OFS(cnk) <= prevChunkOfs) {
            info.numMergedChunks ++;
         }
         prevChunkOfs = CHI_GET_OFS(cnk);
      }
      info.sumChunkSize = pSpline->chunkKeys * info.numChunks;
   }

   return;
}

/***************************************************************
* m3dSPL::GetKpChunk()
*
***************************************************************/
void m3dSPL::GetKpDataChunk(int kp, float * __RESTRICT val) const
{
   CHUNK_SPLINE   *pSpline       = (CHUNK_SPLINE*)pData;
   CHUNK_SCALE    *splTm         = (CHUNK_SCALE*)(pData + sizeof(CHUNK_SPLINE));
   CHUNK_INFO     *chunkTbl      = (CHUNK_INFO*)((BYTE*)splTm + dataDim * sizeof(CHUNK_SCALE));
   CHUNK_INFO     &chunkInfo     = chunkTbl[kp / pSpline->chunkKeys];
   CHUNK_READ_BUF buf; buf.ptr   = pData + CHI_GET_OFS(chunkInfo);

#if (defined _AP_XENON || defined _AP_PS3) && !defined M3D_SUPPRESS_OPTIMIZATION
   // Believe it or not, these table look up shenanigans are faster than
   // the load-hit-stores you'd get writing this code in a sane way.
   static float BYTE_TO_FLOAT[256] =
   {
		0.0f, 1.0f, 2.0f, 3.0f, 4.0f, 5.0f, 6.0f, 7.0f, 8.0f, 9.0f, 10.0f, 
		11.0f, 12.0f, 13.0f, 14.0f, 15.0f, 16.0f, 17.0f, 18.0f, 19.0f, 20.0f, 
		21.0f, 22.0f, 23.0f, 24.0f, 25.0f, 26.0f, 27.0f, 28.0f, 29.0f, 30.0f, 
		31.0f, 32.0f, 33.0f, 34.0f, 35.0f, 36.0f, 37.0f, 38.0f, 39.0f, 40.0f, 
		41.0f, 42.0f, 43.0f, 44.0f, 45.0f, 46.0f, 47.0f, 48.0f, 49.0f, 50.0f, 
		51.0f, 52.0f, 53.0f, 54.0f, 55.0f, 56.0f, 57.0f, 58.0f, 59.0f, 60.0f, 
		61.0f, 62.0f, 63.0f, 64.0f, 65.0f, 66.0f, 67.0f, 68.0f, 69.0f, 70.0f, 
		71.0f, 72.0f, 73.0f, 74.0f, 75.0f, 76.0f, 77.0f, 78.0f, 79.0f, 80.0f, 
		81.0f, 82.0f, 83.0f, 84.0f, 85.0f, 86.0f, 87.0f, 88.0f, 89.0f, 90.0f, 
		91.0f, 92.0f, 93.0f, 94.0f, 95.0f, 96.0f, 97.0f, 98.0f, 99.0f, 100.0f, 
		101.0f, 102.0f, 103.0f, 104.0f, 105.0f, 106.0f, 107.0f, 108.0f, 109.0f, 110.0f, 
		111.0f, 112.0f, 113.0f, 114.0f, 115.0f, 116.0f, 117.0f, 118.0f, 119.0f, 120.0f, 
		121.0f, 122.0f, 123.0f, 124.0f, 125.0f, 126.0f, 127.0f, 128.0f, 129.0f, 130.0f, 
		131.0f, 132.0f, 133.0f, 134.0f, 135.0f, 136.0f, 137.0f, 138.0f, 139.0f, 140.0f, 
		141.0f, 142.0f, 143.0f, 144.0f, 145.0f, 146.0f, 147.0f, 148.0f, 149.0f, 150.0f, 
		151.0f, 152.0f, 153.0f, 154.0f, 155.0f, 156.0f, 157.0f, 158.0f, 159.0f, 160.0f, 
		161.0f, 162.0f, 163.0f, 164.0f, 165.0f, 166.0f, 167.0f, 168.0f, 169.0f, 170.0f, 
		171.0f, 172.0f, 173.0f, 174.0f, 175.0f, 176.0f, 177.0f, 178.0f, 179.0f, 180.0f, 
		181.0f, 182.0f, 183.0f, 184.0f, 185.0f, 186.0f, 187.0f, 188.0f, 189.0f, 190.0f, 
		191.0f, 192.0f, 193.0f, 194.0f, 195.0f, 196.0f, 197.0f, 198.0f, 199.0f, 200.0f, 
		201.0f, 202.0f, 203.0f, 204.0f, 205.0f, 206.0f, 207.0f, 208.0f, 209.0f, 210.0f, 
		211.0f, 212.0f, 213.0f, 214.0f, 215.0f, 216.0f, 217.0f, 218.0f, 219.0f, 220.0f, 
		221.0f, 222.0f, 223.0f, 224.0f, 225.0f, 226.0f, 227.0f, 228.0f, 229.0f, 230.0f, 
		231.0f, 232.0f, 233.0f, 234.0f, 235.0f, 236.0f, 237.0f, 238.0f, 239.0f, 240.0f, 
		241.0f, 242.0f, 243.0f, 244.0f, 245.0f, 246.0f, 247.0f, 248.0f, 249.0f, 250.0f, 
		251.0f, 252.0f, 253.0f, 254.0f, 255.0f
   };
#define WORD_TO_FLOAT(w) (BYTE_TO_FLOAT[(w)&0xFF] + BYTE_TO_FLOAT[((w) >> 8) & 0xFF] * 256.0f)
#endif

   osPrefetch(buf.ptr);

   // read constant tracks, fill base and range for others, calc keypoint size
   int   kpSize         = 0;
   DWORD constMask      = pSpline->constMask;
   DWORD cnkBytes       = CHI_GET_IS_BYTES(chunkInfo);
   DWORD cnkConst       = CHI_GET_IS_CONST(chunkInfo);
   
   float       scale[M3D_SPL_MAX_KP_DIM];

   // read chunk offset and scale for each track
   for (unsigned int t = 0, mask = 1; t < dataDim; t++, mask *= 2) {
      if (constMask & mask) {
         val[t] = splTm[t].base;                            // track is spline-constant -> get value from spline.base[track]
      } else {
#if (defined _AP_XENON || defined _AP_PS3) && !defined M3D_SUPPRESS_OPTIMIZATION
		  WORD wbase = buf.ReadWord();
		  float base = WORD_TO_FLOAT(wbase);
#else
         WORD base   = buf.ReadWord();
#endif
         val[t] = splTm[t].base + base * (1.0f / 64000.0f) * splTm[t].range;
         
         if ((cnkConst & mask) == 0) {
#if (defined _AP_XENON || defined _AP_PS3) && !defined M3D_SUPPRESS_OPTIMIZATION
		  WORD wrange = buf.ReadWord();
		  float range = WORD_TO_FLOAT(wrange);
#else
            WORD range = buf.ReadWord();
#endif
            if ((cnkBytes & mask)) {
               scale[t] = range * (1.0f / 64000.0f / 250.0f) * splTm[t].range;
               kpSize += sizeof(BYTE);
            } else {
               scale[t] = range * (1.0f / 64000.0f / 64000.0f) * splTm[t].range;
               kpSize += sizeof(WORD);
            }
         }
      }
   }

   if (kpSize == 0) {
      // all track are const
      return;
   }

   // read keypoint
   constMask |= cnkConst;

   int subKey = kp % pSpline->chunkKeys;                    // get subkey in this chunk
   buf.Skip(kpSize * subKey);
   osPrefetch(buf.ptr);
   
   for (unsigned int t = 0, mask = 1; t < dataDim; t++, val++, mask *= 2) {
      if (constMask & mask) {
         ;
      } else if (cnkBytes & mask) {
#if (defined _AP_XENON || defined _AP_PS3) && !defined M3D_SUPPRESS_OPTIMIZATION
		 *val += scale[t] * BYTE_TO_FLOAT[buf.ReadByte()];
#else
         *val += scale[t] * buf.ReadByte();
#endif
      } else {
#if (defined _AP_XENON || defined _AP_PS3) && !defined M3D_SUPPRESS_OPTIMIZATION
		  WORD w = buf.ReadWord();
		  *val += scale[t] * WORD_TO_FLOAT(w);
#else
         *val += scale[t] * buf.ReadWord();
#endif
      }
   }

   return;
}

/***************************************************************
* m3dSPL::PackChunks()
*
***************************************************************/
void m3dSPL::PackChunks(int chunkSize, CHUNK_WRITE_BUF &buf, const m3dSPL_OPTIMIZE &opt) const
{
   float    splBase  [M3D_SPL_MAX_KP_DIM];
   float    splRange [M3D_SPL_MAX_KP_DIM];
   DWORD    splConst = 0;

   //DWORD allTrackMask   = (1 << dataDim) - 1;
   DWORD packedTrackMask= (1 << min((int)dataDim, (int)CHUNK_MAX_PACKED_TRACKS)) - 1;

   ASSERT(chunkSize > 2 && chunkSize < 256);

   GetKpDataBaseRange(0, nKp, splBase, splRange);

   // scan for spline-const tracks
   for (int t = 0; t < dataDim; t++) {
      if (splRange[t] < opt.maxErrorConst) {
         // this is a const spline
         splConst |= 1 << t;
      }
   }

   int numChunks = (nKp + chunkSize - 1) / chunkSize;

   // store spline header
   CHUNK_SPLINE spline;
   spline.constMask     = (WORD)splConst;
   spline.chunkKeys     = (BYTE)chunkSize;
   spline.__unsued      = 0;
   buf.StoreBytes(&spline, sizeof(spline));

   // store spline scale info
   {
      CHUNK_SCALE *pScales = buf.At<CHUNK_SCALE>(buf.Reserve(dataDim * sizeof(CHUNK_SCALE)));
      for (int t = 0; t < dataDim; t++) {
         pScales[t].base  = splBase[t];
         pScales[t].range = splRange[t];
      }
   }
   
   // reserve place chunks tbl
   int ofsCnkInfo = buf.Reserve(numChunks * sizeof(CHUNK_INFO));

   // start packing chunks
   for (int cnk = 0; cnk < numChunks; cnk++) {
      float cnkBase   [M3D_SPL_MAX_KP_DIM];
      float cnkRange  [M3D_SPL_MAX_KP_DIM];
      WORD  cnkDiff   [M3D_SPL_MAX_KP_DIM];
      WORD  cnkRng    [M3D_SPL_MAX_KP_DIM];
      
      DWORD cnkConst  = 0;
      DWORD cnkBytes  = 0;

      int k = cnk * chunkSize;
      int numKp = min(chunkSize, nKp - k);

      GetKpDataBaseRange(k, numKp, cnkBase, cnkRange);

      // scan for chunk-const tracks and if tracks that can be byte-packed
      for (int t = 0; t < dataDim; t++) {
         if (splConst & (1 << t)) {
            continue;
         }

         float newBase, newRange;
         
         // calc WORD chunk difference and range
         {
            // pack chunk base minus spline base to word
            float diff = cnkBase[t] - splBase[t];
            ASSERT(diff <= splRange[t] && cnkRange[t] <= splRange[t]);
            
            cnkDiff[t] = (WORD)(diff / splRange[t] * 64000.0f);

            // recalc chunk base
            while (1) {
               newBase = splBase[t] + cnkDiff[t] / 64000.0f * splRange[t];
               if (newBase <= cnkBase[t] || cnkDiff[t] == 0) {
                  break;
               }
               cnkDiff[t]--;
            }
         }
         {  
            // pack chunk range scale to word
            float r = cnkRange[t] + cnkBase[t] - newBase;
            cnkRng[t]   = (WORD)_m3dClamp(0.0f, 64000.0f, r / splRange[t] * 64000.0f + 0.99999f);
            // recalc chunk range
            while (1) {
               newRange = cnkRng[t] / 64000.0f * splRange[t];
               if (newBase + newRange >= cnkBase[t] + cnkRange[t] || cnkRng[t] == 64000) {
                  break;
               }
               cnkRng[t]++;
            }
         }

         if (cnkRng[t] == 0 || newRange < opt.maxErrorConst && t < CHUNK_MAX_PACKED_TRACKS) {
            cnkConst |= 1 << t;
            cnkDiff[t] = (WORD)((cnkBase[t] + cnkRange[t] * 0.5f - splBase[t]) / splRange[t] * 64000.0f);
            cnkRng[t]  = 0;
            continue;
         }

         cnkBase[t]  = newBase;
         cnkRange[t] = newRange;
         
         if (cnkRange[t] / 250.0f < opt.maxErrorPack && t < CHUNK_MAX_PACKED_TRACKS) {
            cnkBytes |= 1 << t;
         }
      }

      // all const tracks can be byte-packed
      cnkBytes |= cnkConst | splConst;

      {
         CHUNK_INFO &info = buf.At<CHUNK_INFO>(ofsCnkInfo)[cnk];
         CHI_SET_IS_BYTES(info, cnkBytes & packedTrackMask);
         CHI_SET_IS_CONST(info, cnkConst & packedTrackMask);
         CHI_SET_OFS(info, buf.dataSize);
         //int a = 0;
      }

      // store chunk stream
      for (int t = 0; t < dataDim; t++) {
         if (splConst & (1<<t)) {
            continue;
         }
         buf.StoreWord(cnkDiff[t]);
         
         if (cnkConst & (1<<t)) {
            continue;
         }
         buf.StoreWord(cnkRng[t]);
      }

      for (int i = 0; i < numKp; i ++) {
         float val[M3D_SPL_MAX_KP_DIM];
         GetKpData(i + k, val);

         for (int t = 0; t < dataDim; t++) {
            if ((splConst | cnkConst) & (1<<t)) {
               continue;
            }

            if (cnkBytes & (1<<t)) {
               float v = (val[t] - cnkBase[t]) / cnkRange[t] * 250.0f;
               ASSERT(v > -0.5f && v < 250.5f);
               buf.StoreByte((BYTE)(v + 0.5f));
            } else {
               float v = (val[t] - cnkBase[t]) / cnkRange[t] * 64000.0f;
               ASSERT(v > -0.5f && v < 64000.5f);
               buf.StoreWord((WORD)(v + 0.5f));
            }
         }
      }
   }

   if (!opt.state.Is(M3D_SPL_OPT_ST_CHUNK_NO_MERGE)) {
      // merge similar chunks
      for (int i = 1; i < numChunks; i++) {
         CHUNK_INFO &cnkToMerge    = buf.At<CHUNK_INFO>(ofsCnkInfo)[i];
         int nextChunkOfs          = (i == numChunks - 1) ? 
                                       buf.dataSize : 
                                       CHI_GET_OFS(buf.At<CHUNK_INFO>(ofsCnkInfo)[i + 1]);
         int        cnkToMergeSize = nextChunkOfs - CHI_GET_OFS(cnkToMerge);
         
         for (int j = i - 1; j >= 0; j--) {
            CHUNK_INFO &cnkToMergeWith     = buf.At<CHUNK_INFO>(ofsCnkInfo)[j];
            int         cnkToMergeWithSize = CHI_GET_OFS(buf.At<CHUNK_INFO>(ofsCnkInfo)[j + 1]) - CHI_GET_OFS(cnkToMergeWith);

            if (cnkToMergeSize != cnkToMergeWithSize) {
               continue;
            }
            if (memcmp(buf.pData + CHI_GET_OFS(cnkToMerge), buf.pData + CHI_GET_OFS(cnkToMergeWith), cnkToMergeSize) != 0) {
               continue;
            }

            // remove chunk data
            memcpy(buf.pData + CHI_GET_OFS(cnkToMerge), buf.pData + nextChunkOfs, buf.dataSize - nextChunkOfs);
            buf.dataSize -= cnkToMergeSize;

            for (int k = i + 1; k < numChunks; k++) {
               CHUNK_INFO &cnk    = buf.At<CHUNK_INFO>(ofsCnkInfo)[k];
               CHI_SET_OFS(cnk, CHI_GET_OFS(cnk) - cnkToMergeSize);
            }

            // redirect chunk
            CHI_SET_OFS(cnkToMerge, CHI_GET_OFS(cnkToMergeWith));

            break;
         }
      }
   }
     
   return;
}

/***************************************************************
* m3dSPL::Optimize()
*
***************************************************************/
void m3dSPL::Optimize(const m3dSPL_OPTIMIZE &opt)
{
   if (nKp <= 1) {
      return;
   }
   
   if (state.Is(M3D_SPL_ST_CHUNKED)) {
      return;
   }

   CheckForConst(opt.maxErrorConst);
      
   if (opt.state.Is(M3D_SPL_OPT_ST_CHUNKS | M3D_SPL_OPT_ST_RAW_REMOVE_ARG | M3D_SPL_OPT_ST_RAW_MAKE_INT_ARG)) {
      // force spline to have int arg
      if (!CheckForIntArg()) {
         // sample spline by 1
         m3dSPL *pSpl = Sample(0, GetKpArg(nKp - 1), 1.0f);
         Swap(pSpl);
         delete pSpl;
      }
   }

   if (opt.state.Is(M3D_SPL_OPT_ST_CHUNKS) && nKp > 4) {
      if (opt.state.Is(M3D_SPL_OPT_ST_HALFRATE) && !state.Is(M3D_SPL_ST_HALFRATE) && nKp > 2) {
         // remove every second key
         m3dSPL *pSpl = Sample(0, GetKpArg(nKp - 1), 2.0f);
         Swap(pSpl);
         delete pSpl;
         state.Set(M3D_SPL_ST_HALFRATE);
      }
         
      // pack spline to chunked form
      CHUNK_WRITE_BUF best, buf;

      int   minChunk, maxChunk, step;
      if (opt.state.IsEach(M3D_SPL_OPT_ST_CHUNK_EVEN_SIZE)) {
         minChunk = opt.minChunk;
         maxChunk = opt.maxChunk;
         step     = 1;
      } else {
         minChunk = opt.minChunk & -2;
         maxChunk = opt.maxChunk & -2;
         step     = 2;
      }

      PackChunks(minChunk, best, opt);
      
      for (int i = minChunk + step; i < maxChunk; i+= step) {
         buf.Clear();
         PackChunks(i, buf, opt);

         if (buf.dataSize <= best.dataSize) {
            CHUNK_WRITE_BUF t = best;
            best = buf;
            buf = t;
            t.pData = NULL;
         }
         
         if (buf.dataSize > best.dataSize * 2) {
            break;         // no chance to find better size
         }
      }

      if (best.dataSize < dataSize) {
         free(pData);
         pData    = best.pData;            
         best.pData = NULL;
         dataSize = best.dataSize;
         state.Set(M3D_SPL_ST_CHUNKED);
         
         m3dSPL_INFO info;
         GetInfo(info);
         sumSplInfo += info;
      }
   }

   // remove arg from raw spline
   if (!state.Is(M3D_SPL_ST_CHUNKED | M3D_SPL_RAW_ST_NO_ARG) && opt.state.Is(M3D_SPL_OPT_ST_RAW_REMOVE_ARG)) {
      ASSERT(CheckForIntArg());
      
      int oldSize = GetRawKpSize();
      state.Set(M3D_SPL_RAW_ST_NO_ARG);
      int newSize = GetRawKpSize();

      ASSERT(newSize < oldSize);
      for (int k = 0; k < nKp; k++) {
         memcpy(pData + k * newSize, pData + k * oldSize + sizeof(float), newSize);
      }

      dataSize = nKp * newSize;
      pData = (BYTE*)realloc(pData, dataSize);
   }

   return;
}

/***************************************************************
* m3dSPL::RemoveRepeatableKeys()
*
***************************************************************/
void m3dSPL::RemoveRepeatableKeys (float acc)
{
   if (nKp <= 2) {
      return;
   }

   float val[M3D_SPL_MAX_KP_DIM];
   GetKpData(0, val);

   int  idxFrom = 0;
   BOOL isStop = FALSE;
   for (int k = 1; k < nKp; k++) {
      float v[M3D_SPL_MAX_KP_DIM];
      GetKpData(k, v);
      for (int t = 0; t < dataDim; t++) {
         if (!m3dIsEqual_A(v[t], val[t], acc)) {
            isStop = TRUE;
            break;
         }
      }

      if (isStop) {
         int size = k - 1 - idxFrom;
         if (size > 0) {
            RemoveKp(idxFrom + 1, size);
            k -= size;
         }

         GetKpData(k, val);
         idxFrom = k;
         isStop = FALSE;
      }
   }

   if (!isStop) {
      int size = nKp - 2 - idxFrom; // do not remove the last key
      if (size > 0) {
         RemoveKp(idxFrom + 1, size);
      }
   }

   return;
}

/***************************************************************
* m3dSPL::CheckForConst()
*
***************************************************************/
BOOL m3dSPL::CheckForConst(float err)
{
   if (nKp < 2) {
      return TRUE;
   }
   
   float val[M3D_SPL_MAX_KP_DIM];
   GetKpData(0, val);

   for (int k = 1; k < nKp; k++) {
      float v[M3D_SPL_MAX_KP_DIM];
      GetKpData(k, v);
      for (int t = 0; t < dataDim; t++) {
         if (!m3dIsEqual_A(v[t], val[t], err)) {
            return FALSE;
         }
      }
   }

   // this spline is constant
   state.Clear(M3D_SPL_ST_CHUNKED);
   
   AllocSpline(1);
   SetKpArg(0, 0.0f);
   SetKpData(0, val);

   return TRUE;
}

/***************************************************************
* m3dSPL::Write()
*
***************************************************************/
void m3dSPL::Write(fioFILE *file)
{
   fioCHUNK cnk;

   file->Write(CNK_SPL_TYPE, type);
   file->Write(CNK_SPL_STATE, state);
   file->Write(CNK_SPL_VALUE_DIM, valDim);
   file->Write(CNK_SPL_DATA_DIM, dataDim);
   file->Write(CNK_SPL_NKP, nKp);
   file->Write(CNK_SPL_DATASIZE, dataSize);
   if (dataSize) {
      file->WriteChunk(CNK_SPL_DATA, &cnk);
         if (file->state.Is(FIO_OPEN_BYTE_REORDER)) {
            ByteReorder();
         }
         file->Write(pData, dataSize);
         if (file->state.Is(FIO_OPEN_BYTE_REORDER)) {
            ByteReorder();
         }
      file->UpdateChunk(&cnk);
   }
   file->WriteLastChunk();
   
   return;
}

/***************************************************************
* m3dSPL::Read()
*
***************************************************************/
m3dSPL* m3dSPL::Read(fioFILE *file)
{
  fioCHUNK cnk;
  m3dSPL *pSpl = NULL;

   // straight by chunks
   while (file->ReadNextChunk(&cnk)) {
      switch (cnk.id) {
         case CNK_SPL_TYPE:
            {
               BYTE  type;
               file->Read(&type);
               pSpl = Make(type);
               ASSERT(pSpl);
            } break;
         case CNK_SPL_STATE:
            ASSERT(pSpl);
            file->Read(pSpl->state);
            break;
         case CNK_SPL_VALUE_DIM:
            ASSERT(pSpl);
            file->Read(&pSpl->valDim);
            break;
         case CNK_SPL_DATA_DIM:
            ASSERT(pSpl);
            file->Read(&pSpl->dataDim);
            break;
         case CNK_SPL_NKP:
            ASSERT(pSpl);
            file->Read(&pSpl->nKp);
            break;
         case CNK_SPL_DATASIZE:
            ASSERT(pSpl);
            file->Read(&pSpl->dataSize);
            pSpl->pData = (BYTE*)realloc(pSpl->pData, pSpl->dataSize);
            break;
         case CNK_SPL_DATA:
            ASSERT(pSpl && pSpl->pData);
            // AK: float to provide info for proper byte reordering
            //file->Read((float*)pSpl->pData, pSpl->dataSize/sizeof(float));
            file->Read(pSpl->pData, pSpl->dataSize);
            break;
         default:
            ASSERT(0);
      }
   }

   if (file->state.Is(FIO_OPEN_BYTE_REORDER)) {
      pSpl->ByteReorder();
   }

   return pSpl;
}

/***************************************************************
* m3dSPL::ReadOld()
*
***************************************************************/
m3dSPL* m3dSPL::ReadOld(int type, fioFILE *file)
{
   int nKp;
   file->Read(&nKp);

   m3dSPL *pSpl = m3dSPL::Make(type, nKp);
   if (!pSpl) {
      file->state.Set(FIO_ERROR);
      return NULL;
   }
   // AK: float to provide info for proper byte reordering
   file->Read((float*)pSpl->pData, pSpl->dataSize/sizeof(float));
   return pSpl;
}


/***************************************************************
* m3dSPL::InterpolateKp()
*
***************************************************************/
void m3dSPL::InterpolateKp(void *kpData1, void *kpData2, float t, void *resKpData) const
{
   for (int i = 0; i < dataDim; i++) {
      ((float*)resKpData)[i] = ((float*)kpData1)[i] + (((float*)kpData2)[i] - ((float*)kpData1)[i]) * t;
   }
   return;
}

__INLINE float m3dLerpFast (float fa, float fb, float a, float b, float t)
{
   ASSERT(b > a);
   return fa + (fb - fa)*(t - a)/(b-a);
}

__INLINE float m3dClampFast (float fa, float fb, float a, float b, float t)
{
   ASSERT(b > a);

   if (t < a) {
      return fa;
   }
   if (t > b) {
      return fb;
   }
   return m3dLerp(fa,fb,a,b,t);
}

/***************************************************************
 * m3dSPL_LINEAR1D::GetValue ()
 *    Get linear spline value
 * IN : arg - argument
 * OUT: pValue    - float value
 *      pValueDif - not filled
 * RET: none
 **************************************************************/
void m3dSPL_LINEAR1D::GetValue (float arg, void* pValue, void *pValueDif) const
{
   int nkp = NKp();

   if (nkp < 6 && !state.Is(M3D_SPL_ST_CHUNKED | M3D_SPL_RAW_ST_NO_ARG)) {
      ASSERT(GetRawKpSize() == sizeof(float) + dataDim * sizeof(float));
      
      m3dSPL_KP_LINEAR1D *kp = (m3dSPL_KP_LINEAR1D*)pData;

      if (arg >= (kp+nkp-1)->arg) {
         *((float*)pValue) = (kp+nkp-1)->value;
         return;
      }
      switch (nkp) {
         case 5:
            if (arg > (kp+3)->arg) {
               *((float*)pValue) = m3dLerpFast((kp+3)->value, (kp+4)->value, (kp+3)->arg, (kp+4)->arg, arg);
               break;
            }
            // don't break
         case 4:
            if (arg > (kp+2)->arg) {
               *((float*)pValue) = m3dLerpFast((kp+2)->value, (kp+3)->value, (kp+2)->arg, (kp+3)->arg, arg);
               break;
            }
            // don't break
         case 3:
            if (arg > (kp+1)->arg) {
               *((float*)pValue) = m3dLerpFast((kp+1)->value, (kp+2)->value, (kp+1)->arg, (kp+2)->arg, arg);
               break;
            }
            // don't break
         case 2:
            if (arg > (kp+0)->arg) {
               *((float*)pValue) = m3dLerpFast(kp->value, (kp+1)->value, kp->arg, (kp+1)->arg, arg);
               break;
            }
            // don't break
         case 1:
            // don't break
            *((float*)pValue) = kp->value;
            break;
         default:
            ASSERT(FALSE);
      }
   } else {
      m3dSPL_KP_LINEAR1D kp0, kp1;
      if (FindSeg(arg, &kp0, &kp1)) {
         *((float*)pValue) = m3dClampFast(kp0.value, kp1.value, kp0.arg, kp1.arg, arg);
      } else {
         *((float*)pValue) = kp0.value;
      }
   }
   return;
}
void m3dSPL_LINEAR1D::SetKp (int kpNmb, float arg, float value)
{
   m3dSPL_KP_LINEAR1D   kp;
   kp.arg      = arg;
   kp.value    = value;
   m3dSPL::SetKp(kpNmb, &kp);
   return;
}
/*
BOOL m3dSPL_LINEAR1D::CompareKP (const m3dSPL_KP *p1, const m3dSPL_KP *p2) const
{
   if (!m3dIsEqual_A(((m3dSPL_KP_LINEAR1D*)p1)->value, ((m3dSPL_KP_LINEAR1D*)p2)->value, 0.0001f)) {
      return FALSE;
   }
   return TRUE;
}
*/

/***************************************************************
 * m3dSPL_LINEAR2D::GetValue ()
 *    Get 2D linear spline value
 * IN : arg - argument
 * OUT: pValue    - m2dV value
 *      pValueDif - not filled
 * RET: none
 **************************************************************/
void m3dSPL_LINEAR2D::GetValue (float arg, void* pValue, void *pValueDif) const
{
   m3dSPL_KP_LINEAR2D kp0, kp1;

   if (FindSeg(arg, &kp0, &kp1)) {
      ((m2dV*)pValue)->x = m3dLerpZero(kp0.value.x, kp1.value.x, kp0.arg, kp1.arg, arg);
      ((m2dV*)pValue)->y = m3dLerpZero(kp0.value.y, kp1.value.y, kp0.arg, kp1.arg, arg);
   } else {
      *((m2dV*)pValue) = kp0.value;
   }
   return;
}
void m3dSPL_LINEAR2D::SetKp (int kpNmb, float arg, const m2dV *value)
{
   m3dSPL_KP_LINEAR2D   kp;
   kp.arg               = arg;
   kp.value             = *value;
   m3dSPL::SetKp(kpNmb, &kp);
   return;
}
void m3dSPL_LINEAR2D::SetKp (int kpNmb, float arg, float x, float y)
{
   m3dSPL_KP_LINEAR2D   kp;
   kp.arg               = arg;
   kp.value.x           = x;
   kp.value.y           = y;
   m3dSPL::SetKp(kpNmb, &kp);
   return;
}
/*
BOOL m3dSPL_LINEAR2D::CompareKP (const m3dSPL_KP *p1, const m3dSPL_KP *p2) const
{
   if (!m2dIsEqualPoint_A(&((m3dSPL_KP_LINEAR2D*)p1)->value, &((m3dSPL_KP_LINEAR2D*)p2)->value, 0.001f)) {
      return FALSE;
   }
   return TRUE;
}
*/

/***************************************************************
 * m3dSPL_LINEAR3D::GetValue ()
 *    Get 3D linear spline value
 * IN : arg - argument
 * OUT: pValue    - m3dV value
 *      pValueDif - not filled
 * RET: none
 **************************************************************/
void m3dSPL_LINEAR3D::GetValue (float arg, void* pValue, void *pValueDif) const
{
   m3dSPL_KP_LINEAR3D kp0, kp1;

   if (FindSeg(arg, &kp0, &kp1)) {
      ((m3dV*)pValue)->x = m3dLerpZero(kp0.value.x, kp1.value.x, kp0.arg, kp1.arg, arg);
      ((m3dV*)pValue)->y = m3dLerpZero(kp0.value.y, kp1.value.y, kp0.arg, kp1.arg, arg);
      ((m3dV*)pValue)->z = m3dLerpZero(kp0.value.z, kp1.value.z, kp0.arg, kp1.arg, arg);
   } else {
      *((m3dV*)pValue) = kp0.value;
   }
   return;
}
void m3dSPL_LINEAR3D::GetValueClosest (float arg, void* pValue, void *pValueDif) const
{
   m3dSPL_KP_LINEAR3D kp0, kp1;

   if (FindSeg(arg, &kp0, &kp1)) {
      if (arg - kp0.arg < kp1.arg - arg) {
         *((m3dV*)pValue) = kp0.value;
      } else {
         *((m3dV*)pValue) = kp1.value;
      }
   } else {
      *((m3dV*)pValue) = kp0.value;
   }
   return;
}
void m3dSPL_LINEAR3D::SetKp (int kpNmb, float arg, const m3dV *value)
{
   m3dSPL_KP_LINEAR3D   kp;
   kp.arg               = arg;
   kp.value             = *value;
   m3dSPL::SetKp(kpNmb, &kp);
}
void m3dSPL_LINEAR3D::SetKp (int kpNmb, float arg, float x, float y, float z)
{
   m3dSPL_KP_LINEAR3D   kp;
   kp.arg               = arg;
   kp.value.x           = x;
   kp.value.y           = y;
   kp.value.z           = z;
   m3dSPL::SetKp(kpNmb, &kp);
   return;
}
/*
BOOL m3dSPL_LINEAR3D::CompareKP (const m3dSPL_KP *p1, const m3dSPL_KP *p2) const
{
   if (!m3dIsEqualPoint_A(&((m3dSPL_KP_LINEAR3D*)p1)->value, &((m3dSPL_KP_LINEAR3D*)p2)->value, 0.003f)) {
      return FALSE;
   }
   return TRUE;
}
*/

/***************************************************************
* m3dSPL_LINEAR3D::DistPoint ()
*   Calculate distance from point to linear spline
* IN  : point - point to calc distance
* OUT : closSegNmb - closest line segment number
*       tMin - closest point in line segment 
*       vClosest  - closest point in 3D
* RET : distance to spline
**************************************************************/
float m3dSPL_LINEAR3D::DistPoint (void *point, int *closSegNmb, float *tMin, void *vClosest) const
{
   int    i, segNmb, minSegNmb;
   int    primeNumber, nSeg;
   float  dist, minDist, t, tM = 0.f;
   m3dV   v0, v1, vClos, v;

   primeNumber = 1299709;
   nSeg        = NKp()-1;

   ASSERT(nSeg < primeNumber);
   minDist   = M3D_INFINITY;
   minSegNmb = -1;
   segNmb = 0;
   for (i = 0; i < nSeg; i ++) {
      // choose line segment randomly
      ASSERT(segNmb == ((i*primeNumber) % nSeg));
      segNmb = (segNmb + primeNumber) % nSeg;

      // get direction of hair segment
      GetKpValue(segNmb,   &v0);
      GetKpValue(segNmb+1, &v1);

      if (m3dDistPointLSeg((m3dV*)point, &v0, &v1, minDist, &dist, &v, &t)) {
         if (minDist > dist) {
            // find a hair with minimal distance to ray
            minDist   = dist;
            vClos     = v;
            tM        = t;
            minSegNmb = segNmb;
         }
      }
   }
   ASSERT(minSegNmb >= 0);

   if (closSegNmb) {
      *closSegNmb = minSegNmb;
   }
   if (tMin) {
      *tMin = tM;
   }
   if (vClosest) {
      *((m3dV*)vClosest) = vClos;
   }
   return minDist;
}
/***************************************************************
 * Hermit splines
 **************************************************************/
/***************************************************************
 * m3dSPL_HERMIT::GetValue ()
 *    Get hermit spline value
 * IN : arg - argument
 * OUT: pValue    - float value
 *      pValueDif - not filled
 * RET: none
 **************************************************************/
void m3dSPL_HERMIT::GetValue (float arg, void* pValue, void *pValueDif) const
{
   m3dSPL_KP_HERMIT  kp0, kp1;
   float      t, pow2, pow3;
   float      coeff_value0, coeff_value1, coeff_slope0, coeff_slope1;
   float      slope0, slope1;

   if (FindSeg(arg, &kp0, &kp1)) {
      // hermit interpolation between neighbour keypoints
      if (m3dIsZero(kp0.arg - kp1.arg)) {
         *((float*)pValue) = (kp0.value + kp1.value) / 2.f;
      } else {
         t = (arg - kp0.arg)/(kp1.arg - kp0.arg);
         ASSERT((t > -M3D_EPSILON) && (t < 1 + M3D_EPSILON));

         slope0 = kp0.slopeRight * (kp1.arg - kp0.arg);
         slope1 = kp1.slopeLeft  * (kp1.arg - kp0.arg);

         pow2 = m3dPow2(t);
         pow3 = pow2 * t;

         coeff_value1 = 2*pow3 - 3*pow2;
         coeff_value0 = coeff_value1 + 1.f;
         coeff_slope1 = pow3 - pow2;
         coeff_slope0 = pow3 - 2*pow2+t;

         *((float*)pValue) = coeff_value0 * kp0.value - coeff_value1 * kp1.value +
                             coeff_slope1 * slope1    + coeff_slope0 * slope0;
      }
   } else {
      *((float*)pValue) = kp0.value;
   }
   return;
}
void m3dSPL_HERMIT::SetKp (int kpNmb, float arg, float value, float slopeLeft, float slopeRight)
{
   m3dSPL_KP_HERMIT  kp;
   kp.arg        = arg;
   kp.value      = value;  
   kp.slopeLeft  = slopeLeft;  
   kp.slopeRight = slopeRight;  
   m3dSPL::SetKp(kpNmb, &kp);
   return;
}
/***************************************************************
 * Lagrange splines
 **************************************************************/
/***************************************************************
 * m3dSPL_LAGRANGE::GetValue ()
 *    Get lagrange spline value
 * IN : arg - argument
 * OUT: pValue    - float value
 *      pValueDif - not filled
 * RET: none
 **************************************************************/
void m3dSPL_LAGRANGE::GetValue (float arg, void* pValue, void *pValueDif) const
{
   m3dSPL_KP_HERMIT  kp0, kp1;
   double     sum = 0.0, product;  // DOUBLE - to prevent floating point errors

   if (!FindSeg(arg, &kp0, &kp1) || m3dIsZero(kp0.arg - arg)) {
      *((float*)pValue) = kp0.value;
   } else if (m3dIsZero(kp1.arg - arg)) {
      *((float*)pValue) = kp1.value;
   } else {
      // calculate Lagrange polynom value
      for (int n = 0; n < NKp(); n ++) {
         m3dSPL::GetKp(n, &kp0);
         product = (double)kp0.value;
         for (int i = 0; i < NKp(); i ++) {
            m3dSPL::GetKp(i, &kp1);
            if (i != n) {
               product *= (double)((arg - kp1.arg))/(double)((kp0.arg - kp1.arg));
            }
         }
         sum += product;
      }
      *((float*)pValue) = (float)sum;
   }
   return;
}
void m3dSPL_LAGRANGE::SetKp (int kpNmb, float arg, float value)
{
   m3dSPL_KP_HERMIT  kp;
   kp.arg            = arg;
   kp.value          = value;  
   return;
}

/***************************************************************
 * Bezier splines
 **************************************************************/
/***************************************************************
 * m3dSPL_BEZIER::GetValueDim ()
 *    Get common bezier spline value
 * IN : arg - argument
 *      dim - spline dimension
 *      vLeft,  vDirLeft  - left keypoint
 *      vRight, vDirRight - right keypoint
 * OUT: pValue    - depends on dimension
 *      pValueDif - spline targent
 * RET: none
 **************************************************************/
void _m3dSPL_BEZIER::CalcValue(float arg, int dim, void* vLeft,  void* vDirLeft, 
                               void* vRight, void* vDirRight, void* pValue, void *pValueD) const
{
   float coeff_vLeft       = 0.f, coeff_vLeft_D       = 0.f;
   float coeff_vRight      = 0.f, coeff_vRight_D      = 0.f;
   float coeff_vDirLeft    = 0.f, coeff_vDirLeft_D    = 0.f;
   float coeff_vDirRight   = 0.f, coeff_vDirRight_D   = 0.f;
   float one_arg, arg_Pow2, one_arg_Pow2;
   int   i;

   if (arg < 0.f || arg > 1.f) {
      ASSERT(FALSE);
      arg = _m3dClamp(0.f, 1.f, arg);
   }

   one_arg      = 1.f-arg;
   arg_Pow2     = arg * arg;
   one_arg_Pow2 = one_arg * one_arg;

   if (pValue) {
      coeff_vLeft     = one_arg_Pow2 * one_arg;     // m3dPow3(1.f-arg);
      coeff_vRight    = arg_Pow2 * arg;             // m3dPow3(arg);
      coeff_vDirLeft  = 3.f * one_arg_Pow2 * arg;   // 3.f*m3dPow2(1.f-arg)*arg;
      coeff_vDirRight = 3.f * one_arg * arg_Pow2;   // 3.f*(1.f-arg)*m3dPow2(arg);

//      coeff_vLeft     = m3dPow3(1.f-arg);
//      coeff_vRight    = m3dPow3(arg);
//      coeff_vDirLeft  = 3.f*m3dPow2(1.f-arg)*arg;
//      coeff_vDirRight = 3.f*(1.f-arg)*m3dPow2(arg);
   }
   if (pValueD) {
      coeff_vLeft_D     = -3.f * one_arg_Pow2;          // -3.f*m3dPow2(1.f-arg);
      coeff_vRight_D    =  3.f * arg_Pow2;              // 3.f*m3dPow2(arg);
      coeff_vDirLeft_D  = -3.f * one_arg * (3.f*arg-1); // 3.f*(arg-1.f)*(3.f*arg-1);
      coeff_vDirRight_D =  3.f * arg * (2.f-3.f*arg);   // 3.f*arg*(2.f-3.f*arg);

//      coeff_vLeft_D     = -3.f*m3dPow2(1.f-arg);
//      coeff_vRight_D    =  3.f*m3dPow2(arg);
//      coeff_vDirLeft_D  =  3.f*(arg-1.f)*(3.f*arg-1);
//      coeff_vDirRight_D =  3.f*arg*(2.f-3.f*arg);
   }
   for (i = 0; i < dim; i ++) {
      if (pValue) {
         m3dVectComponent(pValue, i) = 
            coeff_vLeft      *m3dVectComponent(vLeft    ,i) + 
            coeff_vRight     *m3dVectComponent(vRight   ,i) + 
            coeff_vDirLeft   *m3dVectComponent(vDirLeft ,i) + 
            coeff_vDirRight  *m3dVectComponent(vDirRight,i);
      }
      if (pValueD) {
         m3dVectComponent(pValueD, i) = 
            coeff_vLeft_D      *m3dVectComponent(vLeft    ,i) + 
            coeff_vRight_D     *m3dVectComponent(vRight   ,i) + 
            coeff_vDirLeft_D   *m3dVectComponent(vDirLeft ,i) + 
            coeff_vDirRight_D  *m3dVectComponent(vDirRight,i);
      }
   }
   return;
}

/***************************************************************
 * m3dSPL_BEZIER2D::GetValue ()
 *    Get bezier 2D spline value
 * IN : arg - argument
 * OUT: pValue    - m2dV value
 *      pValueDif - spline targent
 * RET: none
 **************************************************************/
void m3dSPL_BEZIER2D::GetValue (float arg, void *pValue, void *pValueDif) const
{
   int curSegNmb = m3dIntFloor(arg);
   arg = arg - curSegNmb;
   if (curSegNmb == NKp()-1) {
      ASSERT(FALSE);
      curSegNmb --;
      arg ++;
   }

   ASSERT(NKp() >= 2 && curSegNmb >= 0 && curSegNmb < NKp()-1);

   m3dSPL_KP_BEZIER2D kp0, kp1;
   GetKp(curSegNmb, &kp0);
   GetKp(curSegNmb + 1, &kp1);
   CalcValue(arg, 2, &kp0.value, &kp0.dirRight, &kp1.value, &kp1.dirLeft, pValue, pValueDif);


   return;
}
void m3dSPL_BEZIER2D::SetKp (int kpNmb, float arg, const m2dV *value, const m2dV *dirLeft, const m2dV *dirRight)
{
   m3dSPL_KP_BEZIER2D kp;
   kp.arg      = arg;
   kp.value    = *value;  
   kp.dirLeft  = *dirLeft;  
   kp.dirRight = *dirRight;  
   m3dSPL::SetKp(kpNmb, &kp);
   return;
}

/***************************************************************
 * m3dSPL_BEZIER3D::GetValue ()
 *    Get bezier 3D spline value
 * IN : arg - argument
 * OUT: pValue    - m3dV value
 *      pValueDif - spline tangent 
 * RET: none
 **************************************************************/
void m3dSPL_BEZIER3D::GetValue (float arg, void* pValue, void *pValueDif) const
{
   m3dSPL_KP_BEZIER3D kp0, kp1;

   if (FindSeg(arg, &kp0, &kp1)) {
      CalcValue(
         arg, 3, 
         &kp0.value, &kp0.dirRight, 
         &kp0.value, &kp0.dirLeft,
         pValue, pValueDif
         );
   }
   /*
   m3dSPL_KP_BEZIER3D *pKp0, *pKp1;
   int                 curSegNmb;

   curSegNmb = m3dIntFloor(arg);
   arg = arg - curSegNmb;

   if (curSegNmb == NKp() - 1) {
      // instead of taking the first point of the segment beyond last keypoint
      // take the last point of the last segment
      ASSERT(m3dIsZero_A(arg, 0.0001f));
      curSegNmb = NKp() - 2;
      arg = 1.f;
   }
   ASSERT(NKp() >= 2 && curSegNmb >= 0 && curSegNmb <= NKp()-1);
   ASSERT(arg >= 0.f && arg <= 1.f);
   pKp0 = (m3dSPL_KP_BEZIER3D*)operator[](curSegNmb);
   pKp1 = (m3dSPL_KP_BEZIER3D*)operator[](curSegNmb+1);

   GetValueDim(arg, 3, &pKp0->value, &pKp0->dirRight, 
                       &pKp1->value, &pKp1->dirLeft, pValue, pValueDif);
   */
   return;
}
void m3dSPL_BEZIER3D::SetKp (int kpNmb, float arg, const m3dV *value, const m3dV *dirLeft, const m3dV *dirRight)
{
   m3dSPL_KP_BEZIER3D kp;
   kp.arg      = arg;
   kp.value    = *value;  
   kp.dirLeft  = *dirLeft;  
   kp.dirRight = *dirRight;  
   m3dSPL::SetKp(kpNmb, &kp);
   return;
}
/*********************************************************************
* m3dSPL_BEZIER3D::Convert ()
*    Convert spline to type
* IN:  type - destination spline type
*      subdivision - bezier segment subdivision
* RET: new spline 
*********************************************************************/
/*m3dSPL* m3dSPL_BEZIER3D::Convert (int type, int subdivision) 
{ 
   int     nKpNew, kpNmb, i, j;
   float   dist, segLength;
   m3dSPL *pSpl;

   ASSERT(subdivision >= 1);

   switch (type) {
      case M3D_SPL_LINEAR3D:
         nKpNew = (NKp()-1)*subdivision + 1;
         if ((pSpl = m3dSPL::Make(type, nKpNew)) == NULL) {
            return NULL;
         }
         // first point
         kpNmb = 0;
         GetValue(0.f, &m3dSplKpLin3D(pSpl, kpNmb ++)->value);
         for (i = 0; i < NKp()-1; i ++) {
            for (j = 1; j <= subdivision; j ++) {
               GetValue(i + (float)j/subdivision, &m3dSplKpLin3D(pSpl, kpNmb ++)->value);
            }
         }
         ASSERT(kpNmb == nKpNew);
         // calc arguments
         for (i = 0; i < NKp()-1; i ++) {
            segLength = 0.f;
            for (j = 1; j <= subdivision; j ++) {
               dist = m3dDist(&m3dSplKpLin3D(pSpl, i * subdivision + j-1)->value, &m3dSplKpLin3D(pSpl, i * subdivision + j)->value);
               segLength += dist;
            }

            (*pSpl)[i * subdivision]->arg = (float)i;
            for (j = 1; j <= subdivision; j ++) {
               dist = m3dDist(&m3dSplKpLin3D(pSpl, i * subdivision + j-1)->value, &m3dSplKpLin3D(pSpl, i * subdivision + j)->value);
               (*pSpl)[i * subdivision + j]->arg = (*pSpl)[i * subdivision + j-1]->arg + dist / segLength;
            }
         }
         break;
      default:
         ASSERT(FALSE);
         break;
   }
   return pSpl;
}*/
/***************************************************************
 * Quaternion splines
 **************************************************************/
/***************************************************************
 * m3dSPL_QUAT::GetValue ()
 *    Get quaternion spline value
 * IN : arg - argument
 * OUT: pValue    - m3dQUAT value
 *      pValueDif - not filled
 * RET: none
 **************************************************************/
void m3dSPL_QUAT::GetValue (float arg, void* pValue, void *pValueDif) const
{
   m3dSPL_KP_QUAT kp0, kp1;
   float          t;

   if (FindSeg(arg, &kp0, &kp1)) {
		t = (arg - kp0.arg) / (kp1.arg - kp0.arg);
		m3dSlerpQuat(&kp0.value, &kp1.value, t, (m3dQUAT*)pValue);
   } else {
      *((m3dQUAT*)pValue) = kp0.value;
   }
   return;
}
void m3dSPL_QUAT::GetValueClosest (float arg, void* pValue, void *pValueDif) const
{
   m3dSPL_KP_QUAT kp0, kp1;

   if (FindSeg(arg, &kp0, &kp1)) {
      *((m3dQUAT*)pValue) = kp0.value;
   } else {
      if (arg - kp0.arg < kp1.arg - arg) {
         *((m3dQUAT*)pValue) = kp0.value;
      } else {
         *((m3dQUAT*)pValue) = kp1.value;
      }
   }
   return;
}
void m3dSPL_QUAT::SetKp (int kpNmb, float arg, const m3dQUAT *value)
{
   m3dSPL_KP_QUAT    kp;
   kp.arg            = arg;
   kp.value          = *value;
   m3dSPL::SetKp(kpNmb, &kp);
   return;
}
/***************************************************************
* m3dSPL_QUAT::InterpolateKp()
*
***************************************************************/
void m3dSPL_QUAT::InterpolateKp(void *kpData1, void *kpData2, float t, void *resKpData) const
{
   m3dSlerpQuat((m3dQUAT*)kpData1, (m3dQUAT*)kpData2, 2.0f, (m3dQUAT*)resKpData);
   return;
}
/*
BOOL m3dSPL_QUAT::CompareKP (const m3dSPL_KP *p1, const m3dSPL_KP *p2) const
{
   if (!m3dIsEqualQuat_A(&((m3dSPL_KP_QUAT*)p1)->value, &((m3dSPL_KP_QUAT*)p2)->value, 0.003f)) {
      return FALSE;
   }
   return TRUE;
}
*/
/***************************************************************
 * Color spline
 **************************************************************/
/***************************************************************
 * m3dSPL_COLOR::GetValue ()
 *    Get color spline value
 * IN : arg - argument
 * OUT: pValue    - m3dCOLOR value
 *      pValueDif - not filled
 * RET: none
 **************************************************************/
void m3dSPL_COLOR::GetValue (float arg, void* pValue, void *pValueDif) const
{
   m3dSPL_KP_COLOR kp0, kp1;

   if (FindSeg(arg, &kp0, &kp1)) {
      ((m3dCOLOR*)pValue)->r = m3dLerpZero(kp0.value.r, kp1.value.r, kp0.arg, kp1.arg, arg);
      ((m3dCOLOR*)pValue)->g = m3dLerpZero(kp0.value.g, kp1.value.g, kp0.arg, kp1.arg, arg);
      ((m3dCOLOR*)pValue)->b = m3dLerpZero(kp0.value.b, kp1.value.b, kp0.arg, kp1.arg, arg);
      ((m3dCOLOR*)pValue)->a = m3dLerpZero(kp0.value.a, kp1.value.a, kp0.arg, kp1.arg, arg);
   } else {
      *((m3dCOLOR*)pValue) = kp0.value;
   }
   return;
}
void m3dSPL_COLOR::SetKp (int kpNmb, float arg, const m3dCOLOR *value)
{
   m3dSPL_KP_COLOR   kp;
   kp.arg            = arg;
   kp.value          = *value;
   m3dSPL::SetKp(kpNmb, &kp);
   return;
}
void m3dSPL_COLOR::SetKp (int kpNmb, float arg, float r, float g, float b, float a)
{
   m3dSPL_KP_COLOR   kp;
   kp.arg            = arg;
   kp.value.Set(r, g, b, a);
   m3dSPL::SetKp(kpNmb, &kp);
   return;
}

void m3dSPL_COLOR::Scale_0_1(void)
{
   m3dCOLOR c;
   for(int i = 0; i < NKp(); ++i) {
      GetKpValue(i, &c);
      c.Scale_0_1();
      SetKpValue(i, &c);
   }
}

/*
BOOL m3dSPL_COLOR::CompareKP (const m3dSPL_KP *p1, const m3dSPL_KP *p2) const
{
   if (!m3dIsEqualColor_A(&((m3dSPL_KP_COLOR*)p1)->value, &((m3dSPL_KP_COLOR*)p2)->value, 0.003f)) {
      return FALSE;
   }
   return TRUE;
}
*/
/***************************************************************
 * Other functions 
 **************************************************************/

//
// End-of-file 'M3D_SPL.CPP'
//
